package main

import (
	"fmt"
	"sort"
)

func packback_01_q(packSize int, weight, prices []int) int {
	//1.初始化dp数组, 二维数组
	dp := make([][]int, len(weight))
	for i := 0; i < len(weight); i++ {
		dp[i] = make([]int, packSize+1)
	}

	//2. 初始化第一行的dp数组
	for i := weight[0]; i < packSize; i++ {
		dp[0][i] = prices[0]
	}

	//3. 两次循环, 第一层是遍历各种物品，因为第一个物品已经在初始化的时候遍历好了，所以我们直接从1开始
	for i := 1; i < len(weight); i++ {
		//第二层循环是求出各种大小的背包的最大价值
		for j := 0; j <= packSize; j++ {
			if j <= weight[i] {
				dp[i][j] = dp[i-1][j] //直接延续上一个的最大价值
			} else {
				if dp[i-1][j] > dp[i-1][j-weight[i]]+prices[i] {
					dp[i][j] = dp[i-1][j]
					continue
				}
				dp[i][j] = dp[i-1][j-weight[i]] + prices[i]
			}
		}
	}
	return dp[len(weight)-1][packSize]
}

//优化点：01背包的二维数组的递推公式是dp[i] = max(dp[i-1][j-weight[i]] + prices[i], dp[i-1][j]))
//每次都是只用到上一层，所以可以每次都原地进行操作，这样我们的递推公式就变成了 dp[j] = max(dp[j - weight[i]] + prices[i], dp[j])
func packback_01_1dimensional_q(packSize int, weight, prices []int) int {
	//1. 确认dp数组是一维数组 dp[j] j的含义就是背包容量为j时可以存的最大价值
	dp := make([]int, packSize+1)
	//2. 还是一样一样物品拿出来，看下放进去会影响什么
	for i := 0; i < len(weight); i++ {
		//3. 第三层和上面双层的数组有区别，因为只有一层，前面的数据会影响后面的数据，所以要从后面的数据开始填充
		for j := packSize; j >= weight[i]; j-- {
			
			if dp[j-weight[i]]+prices[i] > dp[j] {
				dp[j] = dp[j-weight[i]] + prices[i]
			}
		}
	}
	return dp[packSize]
}

//完全背包，完全背包和01背包的区别在于，物品的数量可以是无限的，也就是说为了能装满，每次可以重复去填充书包
func package_all(packSize int, weight, items []int) int {
	dp := make([]int, packSize + 1) //dp的含义还是当背包大小为i可以最多放多少价值的物品

	for i := 0; i < len(weight); i++ {
		//可以从前往后进行遍历	
		for j := 0; j <= packSize; j ++ {
			if j >= weight[i] {
				if dp[j - weight[i]] + items[i] > dp[j] {
					dp[j] = dp[j - weight[i]] + items[i]
				}
			}
		}
	}

	return dp[packSize]
}

/**
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
**/
func lastStoneWeightII(stones []int) int {
	if len(stones) < 1 {
		return 0
	} 
	
	if len(stones) == 1 {
		return stones[0]
	}

	//这道题可以转化为求解，一个容量为 石头总和一半重量的 背包，如何进行填充
	//第一步，对数组进行排序
	sort.Ints(stones)

	//第三步求解中值
	mid := 0
	for i := 0; i < len(stones); i ++ {
		mid += stones[i]
	}
	sum := mid
	mid /= 2

	//设计dp数组,含义为背包容量为i时最多可以装多沉的石头
	dp := make([]int, mid + 1)
	// for i := 0; i < len(stones); i++ {
	// 	for j := mid; j >= stones[i]; j -- {
	// 		if dp[j - stones[i]] + stones[i] > dp[j] {
	// 			dp[j] = dp[j - stones[i]] + stones[i]
	// 		}
	// 	}
	// }

	for i := 0; i < len(stones); i ++ {
		for j := stones[i]; j <= mid; j ++ {
			if dp[j - stones[i]] + stones[i] > dp[j] {
				dp[j] = dp[j - stones[i]] + stones[i]
			}
		}
	}

	return  sum - dp[mid] - dp[mid]
}


func main() {
	weight := []int{1, 2, 6, 4, 11}
	price := []int{8, 2, 1, 4, 6}

	fmt.Println(packback_01_q(10, weight, price))
	// fmt.Println(packback_01_1dimensional_q(10, weight, price))
	// fmt.Println(package_all(10, weight, price))
	fmt.Println(lastStoneWeightII([]int{2,7,4,1,8,1}))
}
